#include <iostream>
#include <fstream>
#include <string>
#include <conio.h>
using namespace std;

template <class Qtype> class MyQueue {
    typedef struct holder{
        Qtype o;
        holder *next, *prev;
    }HOLDER;

    HOLDER *first, *last;
    int size;


    public:

    MyQueue(){
        first = last = NULL; size = 0;
    }

    ~MyQueue(){

    }

    void enQueue(Qtype newElem){

        size++;
        HOLDER* newHolder = (HOLDER*)malloc(sizeof(HOLDER));
        newHolder->o = newElem;
        newHolder->next = first;
        if(size>1)
            first->prev = newHolder;
        first = newHolder;
        if(size==1)
            last = newHolder;

    }

    void removeLast(){
        HOLDER* tempObj;

        if(first!=NULL){
            tempObj = first->next;
            tempObj->prev = NULL;
            free(first);
            first = tempObj;
            size--;
        }
    }

    Qtype deQueue(){

        Qtype tempObj;

        if(first!=NULL){
            HOLDER* temp = last;
            last = temp->prev;
            size--;
            tempObj = temp->o;
            free(temp);
            return tempObj;
        }
        return NULL;
    }

    int getSize(){
        return size;
    }
};

int main(){
    MyQueue<string> mq;
    MyQueue<string> mq2;

    mq.enQueue("Test");
    mq2.enQueue("Test2");

    cout << mq.deQueue();
    cout << mq2.deQueue();
    return 0;
}
